
#include <cstdlib>
#include <iostream>
#include <vector>
#include <fstream>
#include <math.h>

using namespace std;


void AffichageGraphique(int n, int k, int point[][2], int arbre[][2]);
int construit_arbre(int n, int arbre[][2], int pere[]);
void dijkstra(int n, int point[][2], vector<int> voisin[], int d[], int pere[], int r = 0);
void voisins(int n, int dmax, int point[][2], vector<int> voisins[]);
int distance(int p1[2], int p2[2]);
void pointrandom (int n, int point[][2]);
void AffichageGraphiqueComplet(int n, int m, int point[][2], vector<int> voisins[]);

int main()
{
	int n;                   //Le nombre de points.
	int m;                   //Le nombre d aretes.
	cout << "Entrer le nombre de points: ";
	cin >> n;

	int dmax=50*50;             // La distance jusqu'a laquelle on relie deux points.

	vector<int> voisin[n];   // Les listes de voisins.          
	int point[n][2];         // Les coordonnees des points.

	int d[n];                // La distance a la racine.
	int arbre[n-1][2];       // Les aretes de l'arbre de Dijkstra.
	int pere[n];             // La relation de filiation de l'arbre de Dijkstra.

	pointrandom(n, point);
	voisins(n, dmax, point, voisin);
	AffichageGraphiqueComplet(n, m, point, voisin);
	
	dijkstra(n, point, voisin, d, pere);

	int k = construit_arbre(n, arbre, pere);

	AffichageGraphique(n, k, point, arbre);

	return 0;
}


void pointrandom (int n, int point[][2])
{
	for (int i(0); i < n; i++)
	{
		point[i][0] = rand()%613;
		point[i][1] = rand()%793;
	}
}


void voisins(int n, int dmax, int point[][2], vector<int> voisins[])
{
	for(int i(0); i < n; i++)
	{
		for(int j(0); j<n; j++)
		{
			if(j != i && distance(point[i], point[j]) <= dmax)
			{
				voisins[i].push_back(j);
			}
		}
	}
}

int distance(int p1[2], int p2[2])
{
	return (p2[0] - p1[0]) * (p2[0] - p1[0]) + (p2[1] - p1[1]) * (p2[1] - p1[1]);
}


void AffichageGraphiqueComplet(int n, int m, int point[][2], vector<int> voisins[])
{
	ofstream output;
	output.open("Complet.ps",ios::out);
	output << "%!PS-Adobe-3.0" << endl;
	output << "%%BoundingBox: 0 0 612 792" << endl;
	output << endl;
	for(int i=0;i<n;i++)
	{
		output << point[i][0] << " " << point[i][1] << " 3 0 360 arc" <<endl;
		output << "0 setgray" <<endl;
		output << "fill" <<endl;
		output << "stroke"<<endl;
		output << endl;
	}
	
	output << endl;
	for(int i=0;i<n;i++)
	{
		for(vector<int>::iterator it = voisins[i].begin(); it != voisins[i].end(); ++it)
		{
			output << point[i][0] << " " << point[i][1] 
					<< " moveto" << endl;
			output << point[(*it)][0] << " " << point[(*it)][1] 
					<< " lineto" << endl;
			output << "stroke" << endl;
			output << endl;
		}
	}
}


void dijkstra(int n, int point[][2], vector<int> voisin[], int d[], int pere[], int r)
{
	int traite[n];

 	for(int i(0); i<n; i++)
	{
		d[i] = 99999;
		traite[i] = 0;
		pere[i] = -1;
	}

	pere[r] = r;
	d[r] = 0;

	int x;
	do
	{
		x = -1;

		for(int i(0); i<n; i++)
		{
			if(traite[i] == 0 && (x == -1 || d[i] < d[x]) )
			{
				x = i;
			}
		}

		if(x != -1)
		{
			traite[x] = 1;

			for(vector<int>::iterator it = voisin[x].begin(); it != voisin[x].end(); ++it)
			{
				if(traite[(*it)] == 0 && d[(*it)] > d[x] + distance(point[x], point[(*it)]) )
				{
					d[(*it)] = d[x] + distance(point[x], point[(*it)]);
					pere[(*it)] = x;
				}
			}
		}

	} while(x != -1);

}

int construit_arbre(int n, int arbre[][2], int pere[])
{
	int k(0);

	for(int i(0); i<n; i++)
	{
		if(pere[i] != -1)
		{
			arbre[k][0] = i;
			arbre[k][1] = pere[i];
			k++;
		}
	}

	return k;
}




void AffichageGraphique(int n, int k, int point[][2], int arbre[][2])
{
	ofstream output;
	output.open("Kruskal.ps",ios::out);
	output << "%!PS-Adobe-3.0" << endl;
	output << "%%BoundingBox: 0 0 612 792" << endl;
	output << endl;  
	for(int i=0;i<n;i++)
	{
		output << point[i][0] << " " << point[i][1] << " 3 0 360 arc" <<endl;
		output << "0 setgray" <<endl;
		output << "fill" <<endl;
		output << "stroke"<<endl;
		output << endl;
	}
	
	output << endl;
	for(int i=0;i<k;i++)
	{
		output << point[arbre[i][0]][0] << " " << point[arbre[i][0]][1] 
		<< " moveto" << endl;
		output << point[arbre[i][1]][0] << " " << point[arbre[i][1]][1] 
		<< " lineto" << endl;
		output << "stroke" << endl;
		output << endl;
	}
}



